/*
 * @Author: szx
 * @Date: 2022-04-14 13:47:40
 * @LastEditTime: 2022-04-14 15:22:07
 * @Description:
 * @FilePath: \leetcode\剑指offerII\061\061.js
 */
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number[][]}
 */
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number[][]}
 */
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number[][]}
 */
var kSmallestPairs = function (nums1, nums2, k) {
    const n = nums1.length;
    const m = nums2.length;
    // 求和最小的k 个数对 ： 最大堆
    // 由于数组升序，那么前k 大值 肯定在 nums1 和 nums2 的前k个数据中
    let sum;
    let maxHeap = new MaxHeap(k);
    // 添加一个数组 [sum,num1,num2]
    for (let i = 0; i < k && i < n; i++) {
        for (let j = 0; j < k && j < m; j++) {
            sum = nums1[i] + nums2[j];
            // 插入 arr 通过 sum 进行堆排序
            maxHeap.insert([sum, nums1[i], nums2[j]]);
        }
    }
    const result = [];
    for (let i = maxHeap.size; i >= 1; i--) {
        result.push([maxHeap.data[i][1], maxHeap.data[i][2]]);
    }
    return result;
};

class MaxHeap {
    constructor(maxSize) {
        this.data = [0];
        this.maxSize = maxSize;
        this.size = 0;
    }
    insert(arr) {
        let index = ++this.size;
        while (index > 1) {
            const parentIndex = index >> 1;
            if (arr[0] > this.data[parentIndex][0]) {
                this.data[index] = this.data[parentIndex];
                index = parentIndex;
            } else break;
        }
        this.data[index] = arr;
        if (this.size > this.maxSize) this.delete();
    }
    delete() {
        const temp = this.data.pop();
        let index = 1;
        const size = --this.size;
        while (true) {
            const leftIndex = index * 2;
            const rightIndex = index * 2 + 1;
            let findIndex = index;
            if (leftIndex <= size && this.data[leftIndex][0] > temp[0]) findIndex = leftIndex;
            if (rightIndex <= size && this.data[rightIndex][0] > temp[0]) findIndex = rightIndex;
            // 则要交换
            if (index !== findIndex) {
                this.data[index] = this.data[findIndex];
                index = findIndex;
            } else {
                break;
            }
        }
        this.data[index] = temp; // 找到对应位置后，循环中断，将 temp 的值存储到 当前位置
    }
}
